class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None



class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        # write code here
        if not head:
            return None
        if not head.next:
            return head
        HeadNode = self.ReverseList(head.next)
        head.next.next = head
        head.next=None
        return HeadNode


class LNode(object):
    def __init__(self, data, next=None):
        self.data = data
        self.next = next


class LindedLsit(object):
    def __init__(self):
        self.head = None

    def initList(self, data):
        self.head = LNode(data[0])

        p = self.head
        for i in data[1:]:
            node = LNode(i)
            p.next = node
            p = p.next
        return self.head


def traveList(head):
    # if self.isEmpty():
    #     exit(0)
    p = head
    while p:
        print(p.data)
        p = p.next


class Solution3:
    def ReverseList(self, head: ListNode) -> ListNode:
        # write code here
        if not head:
            return None
        if not head.next:
            return head
        HeadNode = self.ReverseList(head.next)
        head.next.next = head
        print(head)
        head.next = None
        return HeadNode

def reverseN(head,n):
    successor = None
    if n==1:
        successor = head.next
        return head
    last = reverseN(head.next,n-1)
    head.next.next = head
    head.next = successor
    return last


# 链表反转(迭代)
def reverse_iterate(node):
    pre = None
    cur = node
    while cur != None:                         # 遍历链表
        forward = cur.next                     # 储存cur的指针
        cur.next = pre                         # cur指向pre
        pre = cur                              # pre移动到cur的位置
        cur = forward                          # cur移动到下个位置
    return pre



if __name__=="__main__":
    data = [1, 2, 3, 4, 5, 6]
    linked_list = LindedLsit()
    head = linked_list.initList(data)
    # reverseN_head = reverseN(head,3)

    reversed_head = reverse_iterate(head)
    traveList(reversed_head)

